package org.zhenhu.CSCE310.KnapSack;



import java.util.ArrayList;
import java.util.List;




public class KnapSack {
//	public double max;
////	public double totalweight ;
////	public double totalvalue;
//	public ArrayList<Double> list_weight;
	public ArrayList<Double> bestValue;
//	public ArrayList<Double> subweight;
//	public ArrayList<Double> subvalue;
	
	public KnapSack(){
//		this.weight = 0;
//		this.totalvalue = 0;
//		this.bestValue = new ArrayList<Double>(value);
//		this.list_weight = new ArrayList<Double>(weight);

		
	}
	
	public List<Double> knapSack(List<Double> list_value,List<Double> list_weight,double max){
		
		return(knapSack(list_value, list_weight,new ArrayList<Double>(),new ArrayList<Double>(), max,0)); 
	}
	
	
	public List<Double> knapSack(List<Double> list_value,List<Double> list_weight, ArrayList<Double> subweight,ArrayList<Double> subvalue,double max,int index){
		
		
		
		if(weightSum(subweight)> max ){
//			System.out.println("No optial knapsack found");
//			this.bestValue.remove(index);
			return null;
		}else if(valueSum(subvalue)> valueSum(this.bestValue)){
			this.bestValue=new ArrayList<Double>(subvalue);
//			System.out.println("Best value: " + valueSum(this.bestValue) + ", " + "subvalue :" + valueSum(subvalue));
		}
		

		
		
		for(int i= index; i< list_value.size(); i++){
			
			if(weightSum(subweight) + list_weight.get(i)<=max){
			
			subweight.add(list_weight.get(i));
			subvalue.add(list_value.get(i));
			}else{
				continue;
			}
			
//			System.out.println("Subweight: " + subweight);
//			System.out.println(subvalue);
//			this.bestValue=new ArrayList<Double>(subvalue);
//			System.out.println("Best value: " + valueSum(this.bestValue) + ", " + "subvalue :" + valueSum(subvalue));
			
			
//			System.out.println("Best value: " + valueSum(this.bestValue) + ", " + "subvalue :" + valueSum(subvalue));
			
			knapSack(list_value,list_weight,subweight,subvalue,max,i+1);
			
//			System.out.println("Subweight after recursive: " + subweight);
//			System.out.println("value list after recusive: " + subvalue);
//			System.out.println("Best value: " + valueSum(this.bestValue) + ", " + "subvalue :" + valueSum(subvalue));
			
			
			
			
				subweight.remove(subweight.size()-1);
				subvalue.remove(subvalue.size()-1);
			
				
			
			
			
			
			
		}
				

//		System.out.println(this.bestValue);
//		List<Integer> index_list = new ArrayList<Integer>();
//		if(this.bestValue == null){
//			System.out.println("null");
//
//		}else{
//		
//			for(int j=0; j<this.bestValue.size();j++){
//				for(int k=0;k<list_value.size();k++){
//					if(this.bestValue.get(j)==list_value.get(k)){
//						index_list.add(k);
//					}
//				}
//			}
//			System.out.println(index_list);
//		}		
		return bestValue;
	}
	
	public List<Integer> getIndex(List<Double> bestvalue, List<Double> initialWeight){
		
		if(bestvalue == null){
			
			return null;
		}
		
		List<Integer> index = new ArrayList<Integer>();
		for(Double value: bestvalue){
			index.add(initialWeight.indexOf(value));
			initialWeight.set(initialWeight.indexOf(value), Double.MIN_VALUE);
			
		}
		
		return index;
	}
	
	
	//sum of weight list
	public Double weightSum(ArrayList<Double> subweight){
		double totalweight = 0;
		if(subweight == null){
			return 0.0;
		}
			
		for(Double element : subweight){
			totalweight = totalweight+element;
			
		}
		return totalweight;
	}
	
	//sum of the value list
	public Double valueSum(ArrayList<Double> subvalue){
		double totalvalue=0;
		
		if(subvalue == null){
			return 0.0;
		}
		for(Double value : subvalue){
			totalvalue = totalvalue+value;
			
		}
		return totalvalue;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ReadFile.readFile(args[0]);
		
		
		
		
	
		
		

	}

}

